上一回提到大O符號表達執行時間，但對於大O符號我們可能有些疑問。

既是叫時間，那它的單位是什麼？

我們可以在演算法的例子中加入時間來比較一下。

如果今天有一個有100個數字的陣列，我們要在當中找到一個數字。用線性搜尋的話，最多100次操作找到；用二分搜尋則最多7次找到。假設每個步驟要花一毫秒，兩種搜尋分別要用100毫秒和7毫秒，基本上都是一瞬間就完成了，感覺不太出差別。

可是現實案例的輸入會大上很多。

假設輸入的陣列變成有一億個元素，線性搜尋變成要花一億毫秒，相當於要不眠不休持續運算超過24小時，而二分搜尋需要只要大約26毫秒，也是一瞬間就完成。

如果輸入再大一點，變成十億呢？線性搜尋需要超過11天，而二分搜尋卻只要約30毫秒，依然還是一瞬間就完成了。

這樣的比較告訴我們一件重要的事情：

大O符號表達的執行時間沒有秒或毫秒這些單位，因為它的重點並不是在於特定輸入時的執行時間。它的重點在於隨著輸入變大，執行時間會增加多快。

當輸入從100個元素，變成一億個，再變成十億個，O(n)增加很多，O(logn)卻只增加一點點點點，這個差距並不是操作秒數多寡可以影響的。事實上，就算二分搜尋的每個步驟要花到一秒好了，操作十億個元素也只是從30毫秒變成30秒，還是遠遠快於O(n)的11天，說明了兩種執行時間因為增加速度的不同而有根本上的差距。

Algorithms Illuminated 這本書[註1]有很精簡的總結：如果一個演算法的最壞情況執行時間隨著輸入成長得很緩慢，它就算是一個「快的演算法」。

A “fast algorithm” is an algorithm whose worst-case
running time grows slowly with the input size.

為什麼log2 n個步驟寫成執行時間變成O(log n)？

其實這題有點像上一題的延續。上一題提到，不同的執行時間之間有極大差異，而且這個差異會隨著輸入變大而更顯著，所以討論執行時間時，通常只會關注會隨輸入變大會明顯變大的數字，並且忽略其中的常數，也就是那些不會因為輸入變大而改變的數字。

舉例來說，假設玩定時炸彈時，我們用奇數(1, 3, 5, 7...)來猜，因為一次跳兩個數字，應該最多猜50次就會猜到，所以執行時間應該是原本的一半O(n/2)，感覺變快很多。

可是當輸入變成十億，O(n/2)最多仍然要五億次操作，跟O(log n)的30次還是完全不能比，所以在輸入非常大時，可以當作常數(1/2)不會有什麼影響。

因此當用大O符號討論執行時間時，只會留下有決定性影響的部分，去掉常數以及影響較小的n項。例如不管操作次數是n/2或5n+3，仍會說它的執行時間是O(n)；如果是 3n³+n+1，則會說它的執行時間是O(n³)(只留下最高次方的n項)。當然log的底數也是因為同樣原因被去掉，只留下O(log n)。

另外，在執行時間中我們也會看到比較特別的O(1)，代表一個演算法具有常數時間(constant time)。它的意思並不是絕對只要一次操作就可以完成，實際上也有可能是五次或十次，但常數時間的重點在於執行時間不會隨著輸入變大而增加。例如說當我搜尋通訊錄，如果只要輸入朋友的名字「王小新」就可以找到他的電話，那麼無論通訊錄多長，操作時間都不會變，就可以說這個搜尋是O(1)。

• [註1]Tim Roughgarden, Algorithms Illuminated Part 1: The Basics, Soundlikeyourself Publishing, 2017, page 30.